package c_leetcode.a_160_intersection_tow_linked;


import static c_leetcode.a_160_intersection_tow_linked.ListNode.printLiked;

/**
 * 双指针
 * 时间复杂度    O(m+n)
 * 空间复杂度    O(1)
 * ------
 * 思路：
 * Linked A 长度 a | 公共长度 c | A到交点 a-c
 * Linked B 长度 b | 公共长度 c | B到交点 b-c
 * 双指针同步执行，若A先执行完，继续执行B，到相交；对于B类似
 * 相交时，a + b -c = b + a - c
 * 两种情况，存在交点，返回交点值 | 不存在交点，都指向 null
 *
 * @author He Kuntao
 * @since 2025/3/13 10:12
 */
public class DoublePoint {
    public static void main(String[] args) {
        ListNode[] listNode = ListNode.createListNode();
        printLiked(listNode[0], listNode[1]);
        System.out.println(new DoublePoint().getIntersectionNode(listNode[0], listNode[1]));
    }

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode a = headA, b = headB;
        while (a != b) {
            a = a == null ? headB : a.next;
            b = b == null ? headA : b.next;
        }
        return a;
    }

}
